package tear_code_by_hand._01_报数;

/**
 * @author： YHSimon
 * @date： 2022-07-07 21:32
 *
 * 约瑟夫环——公式法（递推公式）  下标从0开始
 * 约瑟夫问题是个著名的问题：N个人围成一圈，第一个人从1开始报数，报M的将被杀掉，下一个人接着从1开始报。如此反复，最后剩下一个，求最后的胜利者。
 */
public class Solution {
    // 递归实现
    public int yuesefu(int n,int m){
        if(n==1){
            return 0;
        }else{
            return (yuesefu(n-1, m)+m)%n;
        }
    }
    // 迭代实现
    public int cir(int n,int m){
        int p=0;
        for(int i=2;i<=n;i++){
            p=(p+m)%i;
        }
        return p;
    }


    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.cir(4, 2));
        System.out.println(s.yuesefu(4, 2));
    }
}
